package com.leetcode.test.queue.BFS;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
import java.util.Set;

/**
 * 广度优先算法 https://leetcode-cn.com/explore/learn/card/queue-stack/217/queue-and-bfs/870/
 */
public class BFS {

	public static void main(String[] args) {
		Node e = new Node("E");
		Node f = new Node("F");
		Node g = new Node("G");

		Node b = new Node("B", Arrays.asList(e));
		Node c = new Node("C", Arrays.asList(e, f));
		Node d = new Node("D", Arrays.asList(g));

		Node a = new Node("A", Arrays.asList(b, c, d));

		System.out.println(BFS(a, g));
	}

	/**
	 * Return the length of the shortest path between root and target node.
	 */
	static int BFS(Node root, Node target) {
		Queue<Node> queue = new ArrayDeque<>();  // store all nodes which are waiting to be processed
		Set<Node>   used  = new HashSet<>();
		int         step  = 0;       // number of steps neeeded from root to current node

		// 添加根节点
		queue.add(root);
		// BFS
		while (!queue.isEmpty()) {
			step = step + 1;
			// iterate the nodes which are already in the queue
			int size = queue.size();

			for (int i = 0; i < size; ++i) {
				// 第一个元素
				Node cur = queue.peek();

				if (cur == target) {
					return step;
				}

				for (Node next : cur.neighbors) {
					if (!used.contains(next)) {
						queue.add(next);
						used.add(next);
					}
				}
				// 移除第一个元素（因此第一个元素移除了，下次peek()是原来的第二个元素）
				queue.poll();
			}
		}
		return -1;          // there is no path from root to target
	}

	static class Node {
		String     name      = "";
		List<Node> neighbors = new ArrayList<>();

		public Node(String name, List<Node> neighbors) {
			this.name = name;
			this.neighbors = neighbors;
		}

		public Node(String name) {
			this.name = name;
		}

		@Override
		public String toString() {
			return name;
		}
	}
}
